package lib

func init() {
	Probs = append(Probs, Problem{
		Num:         924,
		Discription: "一个图种有多个恶意节点，恶意节点会感染所有可联通的节点，改变一个恶意节点的属性使得被干扰的节点数最小，如有多种方案返回索引最小的那个",
		Level:       3,
		Labels: map[string]int{
			"图连通性":   1,
			"递归":1,
		},
	})
}

//通过递归和邻接矩阵将图化成一个个联通的子图：subGraghs
//只考虑恶意节点数量为1的链接子图（没有恶意节点的联通子图没有恶意节点，有两个及以上的恶意节点联通子图改变一个恶意节点后所有节点还是会被感染）
//选出节点数量最多、只有一个恶意节点的联通子图对应的恶意节点
//如果有多个答案，选恶意节点index最小的那个
func MinMalwareSpread(graph [][]int, initial []int) int {
	//联通子图
	subGraghs := make(map[int][]int, 0)
	//每个节点归属的联通子图ID，0表示暂未被处理
	belong := make([]int, len(graph))
	//快速判断每个节点是不是恶意节点
	malMap := make(map[int]bool, len(initial))

	//选出index最小的恶意节点，以面对整个图都联通的情况
	removedIndex := initial[0]
	for _, index := range initial {
		malMap[index] = true
		removedIndex = min(removedIndex, index)
	}

	var dfs func(int, int)
	dfs = func(index int, subIndex int) {
		for i := 0; i < len(graph); i++ {
			if graph[index][i] == 1 && belong[i] == 0 {
				belong[i] = subIndex
                subGraghs[subIndex] = append(subGraghs[subIndex], i)
				dfs(i, subIndex)
			}
		}
	}

	//划分联通子图，子图ID从1开始，默认0表示节点暂未被归类
	subIndex := 1
	for i := 0; i < len(graph); i++ {
		if belong[i] != 0 {
			continue
		}

		belong[i] = subIndex
        subGraghs[subIndex] = append(subGraghs[subIndex], i)
		dfs(i, subIndex)
		subIndex++
	}

	//选出节点数量最多、只有一个恶意节点的联通子图对应的恶意节点
	removedCount := 0
	for _, sub := range subGraghs {
		malCount := 0
		smallestMalIndex := len(graph)
		for _, index := range sub {
			if malMap[index] {
				malCount++
				smallestMalIndex = min(smallestMalIndex, index)
			}
		}

		if malCount == 1 {
			if len(sub) > removedCount {
				removedCount = len(sub)
				removedIndex = smallestMalIndex
			} else if len(sub) == removedCount && removedIndex > smallestMalIndex {
				//如果有多个答案，选恶意节点index数量最小的那个
				removedIndex = smallestMalIndex
			}
		}
	}

	return removedIndex
}